package 力扣.动态规划;

//给定一个整数数组，找出总和最大的连续数列，并返回总和。
public class 连续数列 {
    public static void main(String[] args) {
         int[] nums={-2,1,-3,4,-1,2,1,-5,4};
        int i = maxSubArray(nums);
        System.out.println(i);
    }
    public static int maxSubArray(int[] nums) {
           int n=nums.length;
        int[] dp = new int[n];
        dp[0]=nums[0];
        int res=Integer.MIN_VALUE;
        for (int i = 1; i <n; i++) {
            dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);
            res=Math.max(dp[i],res);
        }
        for (int i = 0; i < n; i++) {
            System.out.print(dp[i]+" ");
        }
        return res>nums[0]?res:nums[0];
    }
}
